//
// Created by fengg on 2020/5/8.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int GetIndex(const char *vets,char vet){
    int i;
    for (i = 0;vets[i]; ++i) {
        if(vets[i] == vet)
            return i;
    }
    return -1;
}


void GenMinTree(int **mat,char *vet,int vet_num, int star_index) {
    unsigned short *book;
    int i,j,k;
    int total=0;
    book = malloc(sizeof(unsigned short)*vet_num);
    memset(book,0,sizeof(unsigned short)*vet_num);
    book[star_index] = 1;
    for (k = 1; k < vet_num; ++k) {
        int min_weight = 9999999;
        int min_start_index = -1;
        int min_end_index = -1;
        for (i = 0; i < vet_num ; ++i ) {
            if(book[i]) {
                for (j = 0; j < vet_num; ++j) {
                    if(mat[i][j] && !book[j]){
                        if(mat[i][j] < min_weight){
                            min_end_index = j;
                            min_start_index = i;
                            min_weight = mat[i][j];
                        }
                    }
                }
            }
        }
        if(min_end_index != -1) {
            printf("(%c,%c)\n",vet[min_start_index],vet[min_end_index]);
            total += mat[min_start_index][min_end_index];
            book[min_end_index] = 1;
        }
    }
    printf("%d",total);
    free(book);
}

int main(){
    char *vet = NULL;
    int **mat = NULL;
    int vet_num,edge_num,i,weight;
    char arc_head,arc_tail,star_vet;
    int arc_head_index,arc_tail_index,star_vet_index;
    scanf("%d %d\n",&vet_num,&edge_num);
    vet = (char *) malloc(sizeof(char)*vet_num+1);
    memset(vet,0, sizeof(char)*vet_num+1);
    mat = (int **)malloc(sizeof(int *)*vet_num);
    for (i = 0; i < vet_num; ++i) {
        mat[i] = malloc(sizeof(int)*vet_num);
        memset(mat[i],0, sizeof(int)*vet_num);
        scanf("%c%*c",&vet[i]);
    }
    for (i = 0; i < edge_num; ++i) {
        scanf("%c %c %d%*c",&arc_head,&arc_tail,&weight);
        arc_head_index = GetIndex(vet,arc_head);
        arc_tail_index = GetIndex(vet,arc_tail);
        mat[arc_head_index][arc_tail_index]
            = weight;
        mat[arc_tail_index][arc_head_index]
                = weight;
    }
    scanf("%c%*c",&star_vet);
    star_vet_index = GetIndex(vet,star_vet);

    GenMinTree(mat,vet,vet_num,star_vet_index);
    for (i = 0; i < vet_num; ++i) {
        free(mat[i]);
    }
    free(mat);
    free(vet);
    return 0;

}
